package com.wangzemin.leetcode.num143;


class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }

        ListNode midPreNode = findMidPreNode(head);
        ListNode lastListHeader = midPreNode.next;
        midPreNode.next = null;

        ListNode revertListHeader = revertList(lastListHeader);

        ListNode mergePoint = new ListNode(-1);
        while (head!=null&&revertListHeader!=null){
            ListNode nextHeader = head.next;
            ListNode nextRevertHeader = revertListHeader.next;
            head.next = null;
            revertListHeader.next=null;

            mergePoint.next = head;
            mergePoint = mergePoint.next;
            mergePoint.next = revertListHeader;
            mergePoint = mergePoint.next;
            head = nextHeader;
            revertListHeader = nextRevertHeader;
        }
        if (revertListHeader!=null){
            revertListHeader.next=null;
            mergePoint.next=revertListHeader;
        }
        if (head!=null){
            head.next=null;
            mergePoint.next=head;
        }
    }

    private ListNode revertList(ListNode lastListHeader) {
        if (lastListHeader == null || lastListHeader.next == null) {
            return lastListHeader;
        }
        ListNode preNode = lastListHeader;
        ListNode nextNode = lastListHeader.next;
        preNode.next = null;
        while (nextNode != null) {
            ListNode nextNextNode = nextNode.next;
            nextNode.next = preNode;
            preNode = nextNode;
            nextNode = nextNextNode;
        }
        return preNode;
    }

    private ListNode findMidPreNode(ListNode head) {
        int length = 0;
        ListNode point = head;
        while (point != null) {
            point = point.next;
            length++;
        }
        int halfLength = length / 2;

        ListNode midPreNode = head;
        while (halfLength > 1) {
            midPreNode = midPreNode.next;
            halfLength--;
        }
        return midPreNode;
    }


    public static void main(String[] args) {

        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        Solution solution = new Solution();
        solution.reorderList(listNode1);
    }
}